// ECE556 - Copyright 2013 University of Wisconsin-Madison.  All Rights Reserved.

#include "ece556.h"
#include "foo.h"
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define LEN     60
#define EDGE_NUM (rst->gx)*(rst->gy - 1) + (rst->gy)*(rst->gx - 1)

routingInst *readBenchmark(const char *fileName)
{
 	routingInst *rst;
        if ( !(rst = (routingInst*)malloc(sizeof(routingInst))))
                exit (0);

        FILE            *fp = fopen (fileName, "r");
        char            line[LEN];

/*************************************************************** 
        rst is the variable to return in this function
****************************************************************/

        int             cap;            //      default capacity
        int             num_net;        //      num net
        int             num_blk = 0;        //      blockage
        int             cnt_net = 0;
        int             cnt_pin = 0;
        int             num_pin = 0;

        point           *node = NULL;

        char    str[LEN];
        while ( fgets (line, LEN, fp) )
        {
                //      read file head
                if (sscanf ( line, "grid\t%d %d", &(rst->gx), &(rst->gy) ))
                {
                        if (!(node = (point*)calloc((rst->gx)*(rst->gy), sizeof(point))))
                                exit (0);
                        int     i, j;
                        for ( i=0; i < rst->gx; ++i )
                                for ( j=0; j < rst->gy; ++j )
                                        assign_point ( node+j+(rst->gy)*i, i, j );
                        if ( !(rst->edgeCaps = (int*)calloc(EDGE_NUM, sizeof(int))))
                                exit (0);
                        if ( !(rst->edgeUtils = (int*)calloc(EDGE_NUM, sizeof(int))))
                                exit (0);
                        if ( !(rst->edgeWeights = (int*)calloc(EDGE_NUM, sizeof(int))))
                                exit (0);
                        continue;
                }       //      gx,gy
                if (sscanf ( line, "capacity\t%d", &cap ))
                {
                        for ( int i = 0; i < EDGE_NUM; ++i )
                        {
                                rst->edgeCaps[i] = cap;
                                rst->edgeUtils[i] = 0;
                        }
                        continue;
                }       //      default capacity
                if (sscanf ( line, "num net %d", &num_net ))
                {
                        if (!(rst->nets = (net*)calloc(num_net, sizeof(net))))
                                exit (0);
                        cnt_net = -1; 
                        continue;
                }       //      num_net
                //      read net information
                if ( !strncmp (line, "n", 1) )
                {
                        ++ cnt_net;
                        char    *first_space = strchr ( line, ' ' );
                        strncpy ( str, first_space+1, LEN );
                        num_pin = atoi (str);
                        rst->nets[cnt_net].id = cnt_net; 
                        rst->nets[cnt_net].numPins = num_pin;
                        if (!(rst->nets[cnt_net].pins = (point*)calloc (num_pin, sizeof(point))))
                                exit (0);
//                        if (!(rst->nets[cnt_net].edgeUtils = (int*)calloc(rst->numEdges,sizeof(int))))
//                                exit (0);
                        cnt_pin = 0;
                        continue;
                }
                /* still reading pin info*/
                if ( (cnt_net < num_net) && (cnt_pin < num_pin) )
                {
                        int     x, y;
                        sscanf (line, "%d %d\n", &x, &y);
                        rst->nets[cnt_net].pins[cnt_pin].x = x;
                        rst->nets[cnt_net].pins[cnt_pin].y = y;
                        ++ cnt_pin;
                        if (cnt_pin == num_pin)         /* finish all pins for a single net */
                        {
//                                find_bb ( rst->nets[cnt_net] ); /* bounding box */
                        }
                        continue;
                }
                if ( !num_blk )
                {
                        num_blk = atoi (line);
                        continue;
                }
                //      read blk info
                int     x1, y1, x2, y2, c;
                sscanf (line, "%d %d %d %d %d", &x1,&y1,&x2,&y2,&c);
                int     edge_id = find_edge_id (x1, y1, x2, y2, rst);
                if ( edge_id == -1 )
                        exit (0); 
                rst->edgeCaps[edge_id] = c;
        }
        rst->cap = cap;
        rst->numNets = num_net;
        rst->numEdges = EDGE_NUM;
        rst->netWeights = new_array (rst->numNets);
        rst->edgeUtils = new_array (EDGE_NUM);
        rst->edgeWeights = new_array (EDGE_NUM);

/* 
 *      Print out of reading benchmark
 */
        printf ( "\nReading Benchmark :\n\n" );
        printf ( "\tGrid dimension :\t%d X %d\n", rst->gx, rst->gy );
        printf ( "\tEdge number :\t\t%d\n", rst->numEdges );
        printf ( "\tNet number :\t\t%d\n", rst->numNets );
        printf ( "\tDefault capacity :\t%d\n", cap );
        printf ( "\tBlockage number :\t%d\n", num_blk );
        
        return  rst;
}
int solveRouting(routingInst *rst)
{
/*************************************************************** 
        initial solution : generate MST for each of nets
****************************************************************/ 
        int     TOT = 0;
        for (int i=0; i < rst->numNets; i++)
        {
                gen_mst ( rst->nets+i, rst );
                TOT += length_int_LL ( (rst->nets+i)->edgeUtils );
                load_int_LL ( (rst->nets+i)->edgeUtils, rst ); 
        }
        printf ( "\nInitial Routing :\n\n");
        printf ( "\tTotal wirelength :\t%d\n", TOT );

        int     old_ofl = ofl (rst);
        int     new_ofl;
        printf ( "\tTotal overflow :\t%d\n", old_ofl );

        cal_netWeights ( rst );
/*************************************************************** 
        improving solution : rip-up and reroute
****************************************************************/ 
        int     *sort = sort_array ( rst->netWeights, rst->numNets );
        
        for (int k=0; k<rst->numNets; ++k)
//                printf ("%d\t%d\t%d\n", k, sort[k], rst->netWeights[sort[k]] );

        rip_up ( rst->nets+sort[0], rst );
        reroute ( rst->nets+sort[0], rst );
        return 1;

        for (int k = 0; k < 1; k++)
        {
                
                for ( int i=0; i < 1; ++i )
                {
                        rip_up ( rst->nets+sort[i], rst );
//                        printf ( "rip_up\n" );
//                        print_result ( stdout, rst );
                        reroute ( rst->nets+sort[i], rst );
//                        printf ( "reroute\n" );
//                        print_result ( stdout, rst );
                        printf ( "Iteration %d : wirelength :%d\t", i, TOT );
                        new_ofl = ofl ( rst );
                        printf ( "overflow :%d\t", new_ofl );
                        if ( new_ofl < old_ofl )
                                printf ("GOOD\n");
                        else
                                printf ("---------BAD\n");
                        old_ofl = new_ofl;
                }
        }
        return 1;

}


	


int writeOutput(const char *outRouteFile, routingInst *rst)
{

       FILE *fp = fopen ( outRouteFile, "w" );
       int net_num = rst -> numNets;	
	for(int i = 0; i < net_num; i ++) {
		net *N = rst -> nets + i;
		int_LL *L = N ->edgeUtils;
		fprintf ( fp, "n%d\n", N->id );
		fprintf(fp, "%d\n",L->num);
		point P1 = find_lower_ponit (L, rst);
		point P2 = find_higher_ponit (L, rst);
		L = L -> next;
		while (L != NULL){
			fprintf(fp, "%d\n",L->num);
			point P3 = find_lower_ponit (L, rst);
			point P4 = find_higher_ponit (L, rst);
			int cmp = compare_point (P2, P3, P4);
			if( cmp )
				P2 = P4;
			else 			
			{	fprintf(fp, "(%d,%d)-(%d,%d)\n", P1.x , P1.y , P2.x, P2.y);
				P1 = P3;
				P2 = P4;
			}
			L = L -> next;
		}
		fprintf(fp, "(%d,%d)-(%d,%d)\n", P1.x , P1.y , P2.x, P2.y);
        	fprintf ( fp, "!\n" );			
	}
	return 1;
}

int release(routingInst *rst)
{
  /*********** TO BE FILLED BY YOU **********/
        free ( rst );
  return 1;
}
